1017E - The Supersonic Rocket - CodeForces Solution

#include <bits/stdc++.h>
using i64 = long long;
using Hash = std::pair<i64, i64>;
std::random_device seed;
std::mt19937_64 rng(seed());

constexpr double eps = 1e-15;
constexpr int N = 1e5 + 10;
constexpr int mod = 469762049;

inline i64 Plus(i64 a, i64 b) {
	return a + b >= mod ? a + b - mod : a + b;
}
inline i64 Minu(i64 a, i64 b) {
	return a - b < 0 ? a - b + mod : a - b;
}

/* Hashing */
Hash operator * (const Hash &a, const Hash &b) {
	return std::make_pair(a.first * b.first % mod, a.second * b.second % mod);
}
Hash operator + (const Hash &a, const Hash &b) {
	return std::make_pair(Plus(a.first, b.first), Plus(a.second, b.second));
}
Hash operator - (const Hash &a, const Hash &b) {
	return std::make_pair(Minu(a.first, b.first), Minu(a.second, b.second));
}

i64 reg(i64 a) {
	return (a % mod + mod) % mod;
}

inline i64 f_pow(i64 a, i64 k) {
	i64 base = 1;
	for (; k; k >>= 1, a = a * a % mod)
		if (k & 1)
			base = base * a % mod;
	return base;
}

struct Point {
	i64 x, y;
	Point() { }
	Point(i64 nx, i64 ny) : x(nx), y(ny) { }
};

using Vector = Point;
Vector operator + (const Vector &a, const Vector &b) {return Vector(a.x + b.x, a.y + b.y);}
Vector operator - (const Vector &a, const Vector &b) {return Vector(a.x - b.x, a.y - b.y);}
Vector operator * (const Vector &a, const int &x) {return Vector(a.x * x, a.x * x);}

i64 Cross(const Vector &A, const Vector &B) {return 1ll * A.x * B.y - 1ll * B.x * A.y;}
i64 Dot(const Vector &A, const Vector &B) {return A.x * B.x + A.y * B.y;}
Vector ft(const Point &A, const Point &B) {return B - A;}

double Length(const Vector &A) {return sqrt(Dot(A, A));}

int n, m;

std::vector<Point> ConvexHull(std::vector<Point> s) {
	auto cmp = [](const Point &a, const Point &b) {
		return a.x == b.x ? a.y < b.y : a.x < b.x;
	};
	std::sort(s.begin(), s.end(), cmp);

	static std::array<Point, N> stk;
	static int tt = 0;
	for (int i = 0; i < s.size(); i++) {
		while (tt > 1 && Cross(ft(stk[tt - 2], stk[tt - 1]), ft(stk[tt - 2], s[i])) <= 0)
			tt--;
		stk[tt++] = s[i];
	}
	int tt2 = tt;
	for (int i = s.size() - 2; i >= 0; i--) {
		while (tt2 > tt && Cross(ft(stk[tt2 - 2], stk[tt2 - 1]), ft(stk[tt2 - 2], s[i])) <= 0)
			tt2--;
		stk[tt2++] = s[i];
	}
	std::vector<Point> vec(tt2);
	for (int i = 0; i < tt2; i++) {
		vec[i] = stk[i];
	}
	tt = 0;
	return vec;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m;
	std::vector<Point> P1(n), P2(m);
	for (auto &[x, y] : P1)
		std::cin >> x >> y;
	for (auto &[x, y] : P2)
		std::cin >> x >> y;

	auto Conv1 = ConvexHull(P1);
	auto Conv2 = ConvexHull(P2);
	
	// 只有两个点
	if (Conv1.size() == Conv2.size() && Conv1.size() == 3) {
		if (fabs(Length(ft(Conv1[0], Conv1[1])) - Length(ft(Conv2[0], Conv2[1]))) <= eps)
			std::cout << "YES\n";
		else
			std::cout << "NO\n";
		return 0;
	}

	int t = Conv1.size() - 1;
	std::vector<Hash> hs(Conv1.size() * 2 - 1);
	Conv1.resize(Conv1.size() * 2 - 1);

	for (int i = t; i < (int)Conv1.size(); i++)
		Conv1[i] = Conv1[i - t];

	Hash base;
	base.first = rng() % 150 + 10;
	base.second = rng() % 150 + 10;
//	std::cerr << '\n' << base.first << ' ' << base.second << '\n';
	Hash ans = std::make_pair(0ll, 0ll);
	for (int i = 1; i < Conv2.size() - 1; i++) {
		auto v1 = ft(Conv2[i], Conv2[i - 1]), v2 = ft(Conv2[i], Conv2[i + 1]);
		i64 val = reg(Dot(v1, v1)) * reg(Dot(v1, v2)) % mod;
		ans = ans * base + std::make_pair(val, val);
	}

	bool flag = false;
	// 其实只有总数 - 1 个角
	Hash basek = std::make_pair(f_pow(base.first, t - 1), f_pow(base.second, t - 1));
	for (int i = 1; i < Conv1.size() - 1; i++) {
		auto v1 = ft(Conv1[i], Conv1[i - 1]), v2 = ft(Conv1[i], Conv1[i + 1]);
		i64 val = reg(Dot(v1, v1)) * reg(Dot(v1, v2)) % mod;
		hs[i] = hs[i - 1] * base + std::make_pair(val, val);
		if (i >= t) {
			auto tmp = hs[i] - (hs[i - (t - 1)] * basek);
			if (tmp == ans) {
				flag = true;
				break;
			}
		}
	}
	if (flag)
		std::cout << "YES" << '\n';
	else
		std::cout << "NO" << '\n';
	return 0;
}